#include "tree.h"

TreeNode* getLeftMinNode(TreeNode* root) {
  while (root->left) {
    root = root->left;
  }

  return root;
}
TreeNode* deleteNode(TreeNode* root, int value) {
  if (root == nullptr) {
    return;
  }

  if (value < root->val) {
    root->left = deleteNode(root->left, value);
  } else if (value > root->val) {
    root->right = deleteNode(root->right, value);
  }

  if (root->left == nullptr) {
    return root->right;
  }
  if (root->right == nullptr) {
    return root->left;
  }

  TreeNode* leftMinNode = getLeftMinNode(root);
  root->val = leftMinNode->val;
  root->left = deleteNode(root->right, leftMinNode->val);
}